\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}

\begin{itemize}
\item
  \(n\) 个点的无向图，起初无任何边
\item
    若 \(u,v\) 之间无边，则为 \(u,v\) 加一条边
\item
    若 \(u,v\) 之间有边，则删除 \(u,v\) 之间的边
\item

    每次操作结束后判断该图此时是否是二分图
\item
  \(2\leq n,q\leq 10^5\)
\end{itemize}

离线。记录每条边添加的时间和删除的时间，然后套线段树时间分治\\
\(tricks\)\\
判断图是否是二分图可以用种类并查集：\\
给 \(u,v\) 之间加边，相当于要让 \(u,v\) 成为敌人，那么只要判断再此之前
\(u,v\) 是否是朋友即可

\begin{lstlisting}
typedef pair<int , int> pii;
const int N = 2e5 + 10;
int n , m;
int far[N] , size[N];
void init()
{
	rep(i , 1 , N - 10) far[i] = i , size[i] = 1;
}
int find(int x)
{
	if(x == far[x]) return x;
	return find(far[x]);
}
void Union(int x , int y , stack<pii>&st)
{
	int tx = find(x) , ty = find(y);
	if(tx != ty)
	{
		if(size[tx] > size[ty]) swap(tx , ty);
		st.push(make_pair(tx , ty));
		far[tx] = ty;
		size[ty] += size[tx];
	}
}
void Redo(stack<pii>&st)
{
	while(!st.empty()) 
	{
		pair<int , int>u = st.top();
		st.pop();
		far[u.fi] = u.fi;
		size[u.se] -= size[u.fi];
	}
}
struct Tree{
	int l , r;
	vector<pii>vec;
}tree[N << 2];
void build(int l , int r , int rt)
{
	tree[rt].l = l , tree[rt].r = r;
	if(l == r) return ;
	int mid = l + r >> 1;
	build(l , mid , rt << 1);
	build(mid + 1 , r , rt << 1 | 1);
}
void update_range(int L , int R , int rt , pii p)
{
	int l = tree[rt].l , r = tree[rt].r;
	if(L <= l && r <= R)
	{
		tree[rt].vec.pb(p);
		return ;
	}
	int mid = l + r >> 1;
	if(L <= mid) update_range(L , R , rt << 1 , p);
	if(R  > mid) update_range(L , R , rt << 1 | 1 , p);
}
void query(int rt , int ok)
{
	int l = tree[rt].l , r = tree[rt].r;
	stack<pii>st;
	for(auto i : tree[rt].vec) 
	{
		if(find(i.fi) == find(i.se)) ok = 0;	
		Union(i.fi , i.se + n , st);
		Union(i.fi + n , i.se , st);
	}		
	if(l == r)
	{
		if(ok) cout << "YES\n";
		else cout << "NO\n";
	}
	else query(rt << 1 , ok) , query(rt << 1 | 1 , ok);
	Redo(st);
}
map<pair<int , int> , int>mp;
signed main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0) , cout.tie(0); 
	init();
	cin >> n >> m;
	build(1 , m , 1);
	rep(i , 1 , m)
	{
		int u , v;
		cin >> u >> v;
		if(u > v) swap(u , v);
		auto it = mp.find(make_pair(u , v));
		if(it != mp.end())
		{
			update_range(it->se , i - 1 , 1 , make_pair(u , v));
			mp.erase(it);
		}
		else mp[make_pair(u , v)] = i;
	}
	for(auto i : mp) update_range(i.se , m , 1 , i.fi);
	query(1 , 1);
	return 0;
}
\end{lstlisting}

\end{document}
